//给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4]
//输出：24
// 
//
// 示例 3： 
//
// 
//输入：nums = [-1,-2,-3]
//输出：-6
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 104 
// -1000 <= nums[i] <= 1000 
// 
// Related Topics 数组 数学 排序 
// 👍 338 👎 0

package com.cute.leetcode.editor.cn;
public class MaximumProductOfThreeNumbers {
    public static void main(String[] args) {
        int[] nums = {1000,1000,2,1,2,5,3,1};
        new MaximumProductOfThreeNumbers().new Solution().maximumProduct(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我是这样写的：先排序，再尝试取值，只不过是自己写的快排
         */
        public int maximumProduct(int[] nums) {
            int len = nums.length;
            quickSort(0, len-1, nums);
            int res1 = nums[0]*nums[1]*nums[len-1];//假设存在至少两个负数，至少一个>=0的数
            int res2 = nums[len-1]*nums[len-2]*nums[len-3];//其他情况都可以这么取
            return Math.max(res1, res2);
        }
        public void quickSort(int left ,int right ,int[] nums){
            int l = left;
            int r = right;
            int pivot = nums[l + (r-l)/2];
            int temp = 0;
            while (l<r){
                while (nums[l]<pivot) l++;
                while (nums[r]>pivot) r--;
                if (l >= r) break;
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;

                if (nums[l]==pivot) r--;
                if (nums[r]==pivot) l++;
            }
            if (l == r){
                l++;
                r--;
            }
            if (l<right) quickSort(l, right, nums);
            if (r>left) quickSort(left, r, nums);
        }

        /**
         * 不排序的方法
         * 找到数组中最大值，二大值，三大值，最小值，次小值
         */
        public int maximumProduct2(int[] nums) {
            int max1 = Integer.MIN_VALUE;
            int max2 = Integer.MIN_VALUE;
            int max3 = Integer.MIN_VALUE;
            int min1 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            for (int num : nums){
                if (num > max1){
                    max3 = max2;
                    max2 = max1;
                    max1 = num;
                }else if (num > max2){
                    max3 = max2;
                    max2 = num;
                }else if (num > max3)
                    max3 = num;
                if (num < min1){
                    min2 = min1;
                    min1 = num;
                }else if (num < min2)
                    min2 = num;
            }
            return Math.max(max1*max2*max3, min1*min2*max1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}